package com.cet.algorithm.链表;

/**
 * @program: algorithm
 * @description: 两链表相交的首个节点
 * @author: 陈恩涛
 * @create: 2022-03-11 21:44
 **/
public class LinkedListInsection {

    /**
     * 提示：相交后，两个链表的后面部分就完全一致了
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        int lengthA = 0;
        int lengthB = 0;
        int delta;
        ListNode p = headA;
        ListNode q = headB;
        ListNode result = null;

        while (p != null) {
            lengthA++;
            p = p.next;
        }

        while (q != null) {
            lengthB++;
            q = q.next;
        }

        if (lengthA > lengthB) {
            delta = lengthA - lengthB;
            q = headB;
            for (p = headA; delta > 0; delta--) {
                p = p.next;
            }
        } else {
            delta = lengthB - lengthA;
            p = headA;
            for (q = headB; delta > 0; delta--) {
                q = q.next;
            }
        }

        for (; p != null; p = p.next, q = q.next) {
            if (p == q) {
                result = p;
                break;
            }
        }

        return result;
    }
}
